4106. Subsets generation

Given a set s of size n, containing all elements from the interval [1 .. n], generate all of its subsets.

Input. One positive integer n (1 ≤ n ≤ 8).

Output. Each subset of the set {1, …, n} should be printed on a separate line. The subset should be printed as a list of its elements in ascending order. The elements of the subset must be written without spaces, i.e., as a concatenated string. Each subset should appear no more than once. The subsets should be listed in ascending order. The empty subset should not be printed.

Sample input	Sample output
3	1 2 3 12 13 23 123

SOLUTION

combinatorics

Algorithm analysis

The task is to generate all subsets of a given set. To do this, iterate through all numbers from 1 to 2ⁿ – 1. Represent the number i in binary and consider its last n bits (which may include leading zeros). Each such binary representation corresponds to a subset: if the k-th bit is set to 1, then the number k (1 ≤ k ≤ n) is included in the subset. For example:

· if n = 3 and i = 2, the binary representation of i = 010₂ corresponds to the subset {2}.

· if n = 4 and i = 11, the binary representation of i = 1011₂ corresponds to the subset {1, 2, 4}.

Example

Let’s consider the generation of subsets for n = 3.

Algorithm implementation

We’ll generate subsets as numbers stored in the array v. For example, the subset {1, 2, 3} will be represented as the number 123.

#define MAX 8

int v[1 << MAX];

Read the input value n.

scanf("%d",&n);

In a loop, iterate through all possible masks for subsets of a set with n elements. The operation 1 << n shifts the number 1 to the left by n positions, which is equivalent to raising 2 to the power of n. Generate all 2ⁿ – 1 subsets (excluding the empty one).

for (i = 1; i < (1 << n); i++)

{

Store the elements of the current subset in the variable x as a string. For example, the subset {1, 2, 4} will be stored as x = 124.

x = 0;

for (j = 0; j < n; j++)

if (i & (1 << j)) x = x * 10 + j + 1;

v[i] = x;

}

Sort the subsets in ascending order based on their corresponding numbers.

sort(v, v + (1 << n));

Print the subsets in the required order.

for (i = 1; i < 1 << n; i++)

printf("%d\n",v[i]);

Java implementation

import java.util.*;

public class Main

{

public static void main(String []args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int v[] = new int[1<<n];

for(int i = 1; i < (1 << n); i++)

{

int val, j;

for(val = j = 0; j < n; j++)

if ((i & (1 << j)) > 0) val = val * 10 + j + 1;

v[i] = val;

}

Arrays.sort(v);

for(int i = 1; i < 1 << n; i++)

System.out.println(v[i]);

con.close();

}

}